{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Valid Move Combinations On Chessboard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #backtracking #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #回溯 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countCombinations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #棋盘上有效移动组合的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个&nbsp;<code>8 x 8</code>&nbsp;的棋盘，它包含&nbsp;<code>n</code>&nbsp;个棋子（棋子包括车，后和象三种）。给你一个长度为 <code>n</code>&nbsp;的字符串数组&nbsp;<code>pieces</code>&nbsp;，其中&nbsp;<code>pieces[i]</code>&nbsp;表示第 <code>i</code>&nbsp;个棋子的类型（车，后或象）。除此以外，还给你一个长度为 <code>n</code>&nbsp;的二维整数数组&nbsp;<code>positions</code>&nbsp;，其中 <code>positions[i] = [r<sub>i</sub>, c<sub>i</sub>]</code>&nbsp;表示第 <code>i</code>&nbsp;个棋子现在在棋盘上的位置为&nbsp;<code>(r<sub>i</sub>, c<sub>i</sub>)</code>&nbsp;，棋盘下标从 <strong>1</strong>&nbsp;开始。</p>\n",
    "\n",
    "<p>棋盘上每个棋子都可以移动 <b>至多一次</b>&nbsp;。每个棋子的移动中，首先选择移动的 <strong>方向</strong>&nbsp;，然后选择 <strong>移动的步数</strong>&nbsp;，同时你要确保移动过程中棋子不能移到棋盘以外的地方。棋子需按照以下规则移动：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>车可以 <strong>水平或者竖直</strong>&nbsp;从&nbsp;<code>(r, c)</code>&nbsp;沿着方向&nbsp;<code>(r+1, c)</code>，<code>(r-1, c)</code>，<code>(r, c+1)</code>&nbsp;或者&nbsp;<code>(r, c-1)</code>&nbsp;移动。</li>\n",
    "\t<li>后可以 <strong>水平竖直或者斜对角</strong>&nbsp;从&nbsp;<code>(r, c)</code> 沿着方向&nbsp;<code>(r+1, c)</code>，<code>(r-1, c)</code>，<code>(r, c+1)</code>，<code>(r, c-1)</code>，<code>(r+1, c+1)</code>，<code>(r+1, c-1)</code>，<code>(r-1, c+1)</code>，<code>(r-1, c-1)</code>&nbsp;移动。</li>\n",
    "\t<li>象可以 <strong>斜对角</strong>&nbsp;从&nbsp;<code>(r, c)</code>&nbsp;沿着方向&nbsp;<code>(r+1, c+1)</code>，<code>(r+1, c-1)</code>，<code>(r-1, c+1)</code>，<code>(r-1, c-1)</code>&nbsp;移动。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>移动组合</strong>&nbsp;包含所有棋子的 <strong>移动</strong>&nbsp;。每一秒，每个棋子都沿着它们选择的方向往前移动 <strong>一步</strong>&nbsp;，直到它们到达目标位置。所有棋子从时刻 <code>0</code>&nbsp;开始移动。如果在某个时刻，两个或者更多棋子占据了同一个格子，那么这个移动组合 <strong>不有效</strong>&nbsp;。</p>\n",
    "\n",
    "<p>请你返回 <strong>有效</strong>&nbsp;移动组合的数目。</p>\n",
    "\n",
    "<p><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>初始时，<strong>不会有两个棋子</strong>&nbsp;在 <strong>同一个位置 。</strong></li>\n",
    "\t<li>有可能在一个移动组合中，有棋子不移动。</li>\n",
    "\t<li>如果两个棋子 <strong>直接相邻</strong>&nbsp;且两个棋子下一秒要互相占据对方的位置，可以将它们在同一秒内 <strong>交换位置</strong>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/23/a1.png\" style=\"width: 215px; height: 215px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pieces = [\"rook\"], positions = [[1,1]]\n",
    "<b>输出：</b>15\n",
    "<b>解释：</b>上图展示了棋子所有可能的移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/23/a2.png\" style=\"width: 215px; height: 215px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pieces = [\"queen\"], positions = [[1,1]]\n",
    "<b>输出：</b>22\n",
    "<b>解释：</b>上图展示了棋子所有可能的移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/23/a3.png\" style=\"width: 214px; height: 215px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pieces = [\"bishop\"], positions = [[4,3]]\n",
    "<b>输出：</b>12\n",
    "<b>解释：</b>上图展示了棋子所有可能的移动。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4:</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/23/a4.png\" style=\"width: 216px; height: 219px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pieces = [\"rook\",\"rook\"], positions = [[1,1],[8,8]]\n",
    "<b>输出：</b>223\n",
    "<b>解释：</b>每个车有 15 种移动，所以总共有 15 * 15 = 225 种移动组合。\n",
    "但是，有两个是不有效的移动组合：\n",
    "- 将两个车都移动到 (8, 1) ，会导致它们在同一个格子相遇。\n",
    "- 将两个车都移动到 (1, 8) ，会导致它们在同一个格子相遇。\n",
    "所以，总共有 225 - 2 = 223 种有效移动组合。\n",
    "注意，有两种有效的移动组合，分别是一个车在 (1, 8) ，另一个车在 (8, 1) 。\n",
    "即使棋盘状态是相同的，这两个移动组合被视为不同的，因为每个棋子移动操作是不相同的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/09/23/a5.png\" style=\"width: 214px; height: 213px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>pieces = [\"queen\",\"bishop\"], positions = [[5,7],[3,4]]\n",
    "<b>输出：</b>281\n",
    "<b>解释：</b>总共有 12 * 24 = 288 种移动组合。\n",
    "但是，有一些不有效的移动组合：\n",
    "- 如果后停在 (6, 7) ，它会阻挡象到达 (6, 7) 或者 (7, 8) 。\n",
    "- 如果后停在 (5, 6) ，它会阻挡象到达 (5, 6) ，(6, 7) 或者 (7, 8) 。\n",
    "- 如果象停在 (5, 2) ，它会阻挡后到达 (5, 2) 或者 (5, 1) 。\n",
    "在 288 个移动组合当中，281 个是有效的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == pieces.length </code></li>\n",
    "\t<li><code>n == positions.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 4</code></li>\n",
    "\t<li><code>pieces</code>&nbsp;只包含字符串&nbsp;<code>\"rook\"</code>&nbsp;，<code>\"queen\"</code>&nbsp;和&nbsp;<code>\"bishop\"</code>&nbsp;。</li>\n",
    "\t<li>棋盘上总共最多只有一个后。</li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 8</code></li>\n",
    "\t<li>每一个&nbsp;<code>positions[i]</code>&nbsp;互不相同。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-valid-move-combinations-on-chessboard](https://leetcode.cn/problems/number-of-valid-move-combinations-on-chessboard/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-valid-move-combinations-on-chessboard](https://leetcode.cn/problems/number-of-valid-move-combinations-on-chessboard/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"rook\"]\\n[[1,1]]', '[\"queen\"]\\n[[1,1]]', '[\"bishop\"]\\n[[4,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "        D1 = [(1,0),(-1,0),(0,1),(0,-1)]\n",
    "        D2 = [(1,1),(1,-1),(-1,1),(-1,-1)]\n",
    "        d = defaultdict(set)\n",
    "        for tp,(r,c) in zip(pieces,positions):\n",
    "            r, c = r-1, c-1\n",
    "            dirs = D1 if tp=='rook' else D2 if tp=='bishop' else D1+D2\n",
    "            for (dx,dy),step in product(dirs,range(8)):\n",
    "                tmp,x,y = [],r,c\n",
    "                for k in range(1,8):\n",
    "                    x,y = (x+dx,y+dy) if k<=step else (x,y)\n",
    "                    if not (0<=x<8 and 0<=y<8):\n",
    "                        break\n",
    "                    tmp.append((x,y))\n",
    "                else:\n",
    "                    d[(r,c)].add(tuple(tmp))\n",
    "        return sum(all(len(set(A))==len(A) for A in zip(*sub)) for sub in product(*d.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "D = {\"rook\":    ((0, 1), (0, -1), (1, 0), (-1, 0)),\n",
    "     \"bishop\":  ((1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "     \"queen\":   ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))}\n",
    "def get_moves(p, x, y):\n",
    "    yield x, y, 0, 0, 0\n",
    "    for t, (dx, dy) in product(range(1, 8), D[p]):\n",
    "        if 1 <= x + dx * t <= 8 and 1 <= y + dy * t <= 8:\n",
    "            yield x, y, dx, dy, t\n",
    "def check(status) -> bool:\n",
    "    for t in range(8):\n",
    "        seen = set()\n",
    "        for x, y, dx, dy, pt in status:\n",
    "            dt = min(t, pt)\n",
    "            if (px := x + dx * dt, py := y + dy * dt) in seen: return False\n",
    "            seen.add((px, py))\n",
    "    return True\n",
    "class Solution:\n",
    "    def countCombinations(self, P: List[str], POS: List[List[int]]) -> int:\n",
    "        return sum(check(status) for status in product(*[get_moves(p, x, y) for p, (x, y) in zip(P, POS)]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "D = {\"rook\":    ((0, 1), (0, -1), (1, 0), (-1, 0)),\r\n",
    "     \"bishop\":  ((1, 1), (1, -1), (-1, 1), (-1, -1)),\r\n",
    "     \"queen\":   ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))}\r\n",
    "    \r\n",
    "def get_moves(p, x, y):\r\n",
    "    yield x, y, 0, 0, 0\r\n",
    "    for t, (dx, dy) in product(range(1, 8), D[p]):\r\n",
    "        if 1 <= x + dx * t <= 8 and 1 <= y + dy * t <= 8:\r\n",
    "            yield x, y, dx, dy, t\r\n",
    "            \r\n",
    "def check(status) -> bool:\r\n",
    "    for t in range(8):\r\n",
    "        seen = set()\r\n",
    "        for x, y, dx, dy, pt in status:\r\n",
    "            dt = min(t, pt)\r\n",
    "            if (px := x + dx * dt, py := y + dy * dt) in seen: return False\r\n",
    "            seen.add((px, py))\r\n",
    "    return True\r\n",
    "    \r\n",
    "class Solution:\r\n",
    "    def countCombinations(self, P: List[str], POS: List[List[int]]) -> int:\r\n",
    "        return sum(check(status) for status in product(*[get_moves(p, x, y) for p, (x, y) in zip(P, POS)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "D = {\"rook\":    ((0, 1), (0, -1), (1, 0), (-1, 0)),\n",
    "     \"bishop\":  ((1, 1), (1, -1), (-1, 1), (-1, -1)),\n",
    "     \"queen\":   ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1))}\n",
    "def get_moves(p, x, y):\n",
    "    yield x, y, 0, 0, 0\n",
    "    for t, (dx, dy) in product(range(1, 8), D[p]):\n",
    "        if 1 <= x + dx * t <= 8 and 1 <= y + dy * t <= 8:\n",
    "            yield x, y, dx, dy, t\n",
    "def check(status) -> bool:\n",
    "    for t in range(8):\n",
    "        seen = set()\n",
    "        for x, y, dx, dy, pt in status:\n",
    "            dt = min(t, pt)\n",
    "            if (px := x + dx * dt, py := y + dy * dt) in seen: return False\n",
    "            seen.add((px, py))\n",
    "    return True\n",
    "class Solution:\n",
    "    def countCombinations(self, P: List[str], POS: List[List[int]]) -> int:\n",
    "        return sum(check(status) for status in product(*[get_moves(p, x, y) for p, (x, y) in zip(P, POS)]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "\n",
    "        dct = dict()\n",
    "        dct[\"rook\"] = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        dct[\"queen\"] = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, 1], [1, 1], [1, -1], [-1, -1]]\n",
    "        dct[\"bishop\"] = [[-1, 1], [1, 1], [1, -1], [-1, -1]]\n",
    "\n",
    "        ans = 0\n",
    "        n = len(pieces)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans += 1\n",
    "                return\n",
    "            x, y = positions[i]\n",
    "            cnt = 0\n",
    "            for a, b in dct[pieces[i]]:\n",
    "                for step in range(8):\n",
    "                    if step == 0 and cnt:\n",
    "                        continue\n",
    "                    cnt += 1\n",
    "                    if not (1 <= x + a * step <= 8 and 1 <= y + b * step <= 8):\n",
    "                        break\n",
    "                    lst = [(x + a * s, y + b * s) for s in range(step + 1)]\n",
    "                    while len(lst) < 8:\n",
    "                        lst.append(lst[-1])\n",
    "                    for ii, w in enumerate(lst):\n",
    "                        if w in pre[ii]:\n",
    "                            break\n",
    "                    else:\n",
    "                        for ii, w in enumerate(lst):\n",
    "                            pre[ii].add(w)\n",
    "                        dfs(i + 1)\n",
    "                        for ii, w in enumerate(lst):\n",
    "                            pre[ii].discard(w)\n",
    "\n",
    "            return\n",
    "\n",
    "        pre = [set() for _ in range(8)]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "        n = len(pieces)\n",
    "\n",
    "        def sim(ds, ts, ps):\n",
    "            nps = []\n",
    "            nts = []\n",
    "\n",
    "            occu = set()\n",
    "            todo = n\n",
    "            for i in range(n):\n",
    "                dx, dy = ds[i]\n",
    "                x, y = ps[i]\n",
    "                t = ts[i]\n",
    "\n",
    "                if t > 0:\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    todo -= 1\n",
    "                    \n",
    "                if (x, y) in occu:\n",
    "                    return 0\n",
    "\n",
    "                occu.add((x, y))\n",
    "                nps.append((x, y))\n",
    "                nts.append(t)\n",
    "\n",
    "            if todo == 0:\n",
    "                return 1\n",
    "\n",
    "            return sim(ds, nts, nps)\n",
    "\n",
    "        moves = []\n",
    "        for i in range(n):\n",
    "            moves.append([(0, 0, 0)])\n",
    "            x, y = positions[i]\n",
    "            if pieces[i] == 'rook':\n",
    "                for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0)):\n",
    "                    for t in range(1, 8):\n",
    "                        if 0 < x + dx * t < 9 and 0 < y + dy * t < 9:\n",
    "                            moves[i].append((dx, dy, t))\n",
    "                        else:\n",
    "                            break\n",
    "\n",
    "            elif pieces[i] == 'queen':\n",
    "                for dx, dy in ((0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)):\n",
    "                    for t in range(1, 8):\n",
    "                        if 0 < x + dx * t < 9 and 0 < y + dy * t < 9:\n",
    "                            moves[i].append((dx, dy, t))\n",
    "                        else:\n",
    "                            break\n",
    "            elif pieces[i] == 'bishop':\n",
    "                for dx, dy in ((1, 1), (1, -1), (-1, 1), (-1, -1)):\n",
    "                    for t in range(1, 8):\n",
    "                        if 0 < x + dx * t < 9 and 0 < y + dy * t < 9:\n",
    "                            moves[i].append((dx, dy, t))\n",
    "                        else:\n",
    "                            break\n",
    "\n",
    "        ret = 0\n",
    "        def dfs(idx, path):\n",
    "            nonlocal ret\n",
    "\n",
    "            if idx == n:\n",
    "                ds = [(x, y) for x, y, z in path]\n",
    "                ts = [z for x, y, z in path]\n",
    "                ps = list(positions)\n",
    "\n",
    "                if sim(ds, ts, ps) == 1:\n",
    "                    ret += 1\n",
    "\n",
    "                return\n",
    "                \n",
    "            for dx, dy, t in moves[idx]:\n",
    "                path.append((dx, dy, t))\n",
    "                dfs(idx + 1, path)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(0, [])\n",
    "\n",
    "        return ret\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "\n",
    "        dct = dict()\n",
    "        dct[\"rook\"] = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        dct[\"queen\"] = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, 1], [1, 1], [1, -1], [-1, -1]]\n",
    "        dct[\"bishop\"] = [[-1, 1], [1, 1], [1, -1], [-1, -1]]\n",
    "\n",
    "        ans = 0\n",
    "        n = len(pieces)\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans += 1\n",
    "                return\n",
    "            x, y = positions[i]\n",
    "            lst = [(x, y)]*10\n",
    "            for ii, w in enumerate(lst):\n",
    "                if w in pre[ii]:\n",
    "                    break\n",
    "            else:\n",
    "                for ii, w in enumerate(lst):\n",
    "                    pre[ii].add(w)\n",
    "                dfs(i + 1)\n",
    "                for ii, w in enumerate(lst):\n",
    "                    pre[ii].discard(w)\n",
    "\n",
    "            for a, b in dct[pieces[i]]:\n",
    "                for step in range(1, 10):\n",
    "                    if not (1 <= x + a * step <= 8 and 1 <= y + b * step <= 8):\n",
    "                        break\n",
    "                    lst = [(x + a * s, y + b * s) for s in range(step + 1)]\n",
    "                    while len(lst) < 10:\n",
    "                        lst.append(lst[-1])\n",
    "                    for ii, w in enumerate(lst):\n",
    "                        if w in pre[ii]:\n",
    "                            break\n",
    "                    else:\n",
    "                        for ii, w in enumerate(lst):\n",
    "                            pre[ii].add(w)\n",
    "                        dfs(i + 1)\n",
    "                        for ii, w in enumerate(lst):\n",
    "                            pre[ii].discard(w)\n",
    "\n",
    "            return\n",
    "\n",
    "        pre = defaultdict(set)\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dct = dict()\n",
    "dct[\"rook\"] = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "dct[\"queen\"] = [[-1, 0], [1, 0], [0, -1], [0, 1], [-1, -1], [-1, 1], [1, -1], [1, 1]]\n",
    "dct[\"bishop\"] = [[-1, -1], [-1, 1], [1, -1], [1, 1]]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        n = len(pieces)\n",
    "\n",
    "        def check():\n",
    "            m = max(len(w) for w in pre)\n",
    "            pos_set = defaultdict(set)\n",
    "            for i in range(n):\n",
    "                k = len(pre[i])\n",
    "                for j in range(m):\n",
    "                    if j < k:\n",
    "                        a, b = pre[i][j][:]\n",
    "                    else:\n",
    "                        a, b = pre[i][-1][:]\n",
    "                    if (a, b) in pos_set[j]:\n",
    "                        return 0\n",
    "                    pos_set[j].add((a, b))\n",
    "            return 1\n",
    "\n",
    "        def dfs(i):\n",
    "            nonlocal ans\n",
    "            if i == n:\n",
    "                ans += check()\n",
    "                return\n",
    "            x, y = positions[i]\n",
    "            w = 0\n",
    "\n",
    "            for a, b in dct[pieces[i]]:\n",
    "                lst = [[x, y]]\n",
    "                for r in range(1, 10):\n",
    "                    if 1 <= x + a * r <= 8 and 1 <= y + b * r <= 8:\n",
    "                        lst.append([x + a * r, y + b * r])\n",
    "                        pre.append(copy.deepcopy(lst))\n",
    "                        dfs(i + 1)\n",
    "                        w += 1\n",
    "                        pre.pop()\n",
    "\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "            lst = [[x, y]]\n",
    "            pre.append(copy.deepcopy(lst))\n",
    "            dfs(i + 1)\n",
    "            pre.pop()\n",
    "            w += 1\n",
    "    \n",
    "            return\n",
    "\n",
    "        pre = []\n",
    "        dfs(0)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countCombinations(self, pieces: List[str], positions: List[List[int]]) -> int:\n",
    "        def dfs(idx):#棋子下标\n",
    "            if idx == l:#如果所有棋子都已落子，此方案可行，返回1\n",
    "                return 1\n",
    "            i, j = positions[idx]#棋子的初始位置\n",
    "            res = 0\n",
    "            if all(visit[i][j][k] == 0 for k in range(8)):#如果棋子当前位置上所有时间状态位都不存在棋子才可以落子，否则会相遇。\n",
    "                for k in range(8):#回溯标记，由于棋子不动，所以8个状态位都是满的\n",
    "                    visit[i][j][k] = 1\n",
    "                res += dfs(idx + 1)#继续搜索\n",
    "                for k in range(8):#取消标记\n",
    "                    visit[i][j][k] = 0\n",
    "            if pieces[idx] == \"rook\":#根据棋子选择棋子的方向\n",
    "                it = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n",
    "            elif pieces[idx] == \"bishop\":\n",
    "                it = [[1, 1], [1, -1], [-1, 1], [-1, -1]]\n",
    "            else:\n",
    "                it = [[1, 0], [0, 1], [-1, 0], [0, -1], [1, 1], [1, -1], [-1, 1], [-1, -1]]\n",
    "            for dx, dy in it:#遍历所有的方向\n",
    "                x, y, c = i, j, 0 #分别是起始位置和时间状态\n",
    "                tmp = [] #用于记录行进路径\n",
    "                while 0 <= x + dx < 8 and 0 <= y + dy < 8 and visit[x + dx][y + dy][c] == 0: #需要满足移动的新位置的时间状态下不存在棋子\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    c += 1\n",
    "                    visit[x][y][c - 1] = 1#移动后需要标记当前时间状态\n",
    "                    tmp.append([x, y, c - 1])#移动状态会维持到落子之后，需要在此方向遍历结束后才能取消标记，所以在这里先记录\n",
    "                    if all(visit[x][y][k] == 0 for k in range(c, 8)):#如果之后的时间状态也不存在棋子，所以可以落子\n",
    "                        for k in range(c, 8):#标记后续状态\n",
    "                            visit[x][y][k] = 1\n",
    "                        res += dfs(idx + 1)#继续搜索\n",
    "                        for k in range(c, 8):#取消标记\n",
    "                            visit[x][y][k] = 0\n",
    "                for x, y, k in tmp:#将行进路径上的所有状态取消标记\n",
    "                    visit[x][y][k] = 0\n",
    "            return res\n",
    "        l = len(pieces)\n",
    "        positions = [[i - 1, j - 1] for i, j in positions]#坐标-1，方便计算\n",
    "        visit = [[[0 for i in range(8)] for j in range(8)] for k in range(8)]#visit标记\n",
    "        return dfs(0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
